package com.situ.day26;

import java.lang.String;

public class Demo {
    private static int count = 0;

    public static void main(String[] args) {
        int result = factorial(5);
        System.out.println(result);

        // show();
    }

    // n!=n*(n-1)*(n-2)*...*3*2*1
    // factorial(5) = 5*factorial(4)
    // factorial(4) = 4**factorial(3)
    // factorial(3) = 3*factorial(2)
    // factorial(2) = 2*factorial(1)
    // factorial(1) = 1
    public static int factorial(int n) {
        if (n == 1) {// 递归退出的条件
            return 1;
        }

        return n * factorial(n - 1);
    }

    public static void show() {
        count++;
        System.out.println("count: " + count);
        show();
    }

    public static int fibonacci(int n) {
        if (n == 0 || n == 1) {
            return n;
        }

        return fibonacci(n - 1) + fibonacci(n - 2);
    }


    public static void main2(String[] args) {
        int[] array = new int[] { 8, 17, 19, 37, 40, 73, 79, 82, 87, 95, 97, 98 };
        int target = 95;
        int low = 0;
        int high = array.length - 1;
        // 找到了返回索引位置，找不到返回-1
        int index = binarySearch(array, target, low, high);
        System.out.println(index);
    }


    private static int binarySearch(int[] array, int target, int low, int high) {
        System.out.println("low: " + low);
        System.out.println("high: " + high);
        // 递归退出的条件
        if (low > high) {
            return  -1;
        }

        int mid = (low + high) / 2;
        if (target > array[mid]) {
            return binarySearch(array, target, mid + 1, high);
        } else if (target < array[mid]) {
            return  binarySearch(array, target, low, mid - 1);
        } else {// target == array[mid]
            return mid;
        }
    }
}
